package algorithms.tree;

import java.util.Stack;

public class BtreeUtils {

    /**
     * 二叉树的先序递归遍历
     * 头-》左子树-》右子树
     *
     * @param root
     */
    public static void preorderForeachRecursion(Node<?> root) {
        if (root == null) {
            return;
        }
        System.out.print(root.getValue()+"-> ");// 输出
        preorderForeachRecursion(root.getLeft());// 遍历左边
        preorderForeachRecursion(root.getRight());// 遍历右边
    }

    /**
     * 二叉树的先序遍历 非递归方式：利用栈
     *
     * 先把头入栈
     * 1.从栈中弹出一个节点---》打印
     * 2.先右再左（如果有）入栈
     * 重复 1，2
     */
    public static void preorderForeach(Node<?> root) {
        Stack<Node> stack = new Stack<>();
        // 先把头入栈
        stack.push(root);
        while (!stack.isEmpty()) {
            // 1.从栈中弹出一个节点---》打印
            Node curr = stack.pop();
            System.out.print(curr.getValue()+"-> ");
            // 2.先右再左（如果有）入栈
            if( curr.getRight() != null ) {
                stack.push(curr.getRight());
            }
            if( curr.getLeft() != null ) {
                stack.push(curr.getLeft());
            }
            // 重复 1，2
        }

    }


    /**
     * 二叉树的中序递归遍历
     * 左树-》头-》右树
     *
     * @param root
     */
    public static void inorderForeach(Node<?> root) {
        if (root == null) {
            return;
        }
        inorderForeach(root.getLeft());// 遍历左边
        System.out.print(root.getValue()+"-> ");// 输出
        inorderForeach(root.getRight());// 遍历右边
    }

    /**
     * 二叉树的后序递归遍历
     * 左->右->头
     *
     * @param root
     */
    public static void postorderForeach(Node<?> root) {
        if (root == null) {
            return;
        }
        postorderForeach(root.getLeft());// 遍历左边
        postorderForeach(root.getRight());// 遍历右边
        System.out.print(root.getValue()+"-> ");// 输出
    }
}
